package leetcode_core.leetcode_2;

import java.util.*;

public class CombinationSum3 {

    private List<List<Integer>> ans = new ArrayList<>();
    private boolean[] book = new boolean[10];

    public List<List<Integer>> combinationSum3(int k, int n) {
        backtrack(n,k,new LinkedList<>(),1);
        return ans;
    }

    private void backtrack(int target, int k, LinkedList<Integer> track,int start){
        if(target == 0 && track.size() == k){
            ans.add(new ArrayList<>(track));
            return;
        }
        if(target<0 || track.size() >k){
            return;
        }
        for(int i =start;i<=9;i++){
            if(book[i]){
                continue;
            }
            //做选择
            track.add(i);
            book[i] = true;
            //递归回溯
            backtrack(target-i,k,track,i+1);
            //撤销选择
            track.removeLast();
            book[i] = false;
        }
    }




}
